{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Linked List Already Sorted Using Absolute Values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortLinkedList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给按照绝对值排序的链表排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个链表的头结点&nbsp;<code>head</code>&nbsp;，这个链表是根据结点的<strong>绝对值</strong>进行<strong>升序</strong>排序, 返回重新根据<strong>节点的值</strong>进行<strong>升序</strong>排序的链表。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/10/17/image-20211017201240-3.png\" style=\"width: 621px; height: 250px;\">\n",
    "<pre><strong>输入:</strong> head = [0,2,-5,5,10,-10]\n",
    "<strong>输出:</strong> [-10,-5,0,2,5,10]\n",
    "<strong>解释:</strong>\n",
    "根据结点的值的绝对值排序的链表是 [0,2,-5,5,10,-10].\n",
    "根据结点的值排序的链表是 [-10,-5,0,2,5,10].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/10/17/image-20211017201318-4.png\" style=\"width: 338px; height: 250px;\"></p>\n",
    "\n",
    "<pre><strong>输入:</strong> head = [0,1,2]\n",
    "<strong>输出:</strong> [0,1,2]\n",
    "<strong>解释:</strong>\n",
    "这个链表已经是升序的了。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> head = [1]\n",
    "<strong>输出:</strong> [1]\n",
    "<strong>解释:</strong>\n",
    "这个链表已经是升序的了。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表节点数的范围是&nbsp;<code>[1, 10<sup>5</sup>]</code>.</li>\n",
    "\t<li><code>-5000 &lt;= Node.val &lt;= 5000</code></li>\n",
    "\t<li><code>head</code>&nbsp;是根据结点绝对值升序排列好的链表.</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>进阶:</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以在<code>O(n)</code>的时间复杂度之内解决这个问题吗?</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-linked-list-already-sorted-using-absolute-values](https://leetcode.cn/problems/sort-linked-list-already-sorted-using-absolute-values/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-linked-list-already-sorted-using-absolute-values](https://leetcode.cn/problems/sort-linked-list-already-sorted-using-absolute-values/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,2,-5,5,10,-10]', '[0,1,2]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur = head\n",
    "        while 1:\n",
    "            if cur.next and cur.next.val < 0:\n",
    "                tmp = cur.next \n",
    "                cur.next = cur.next.next\n",
    "                tmp.next = head \n",
    "                head = tmp \n",
    "            else:\n",
    "                cur = cur.next \n",
    "            if not cur:\n",
    "                break \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        curr = dummy = ListNode(next=head)\n",
    "        neg = ListNode()\n",
    "        \n",
    "        while curr and curr.next:\n",
    "            if curr.next.val >= 0:\n",
    "                curr = curr.next\n",
    "            else:\n",
    "                next = curr.next\n",
    "                curr.next = next.next\n",
    "                next.next = neg.next\n",
    "                neg.next = next\n",
    "\n",
    "        curr = neg\n",
    "        while curr.next:\n",
    "            curr = curr.next\n",
    "\n",
    "        curr.next = dummy.next\n",
    "        return neg.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        dummy1=ListNode(0,head)\n",
    "        dummy2=ListNode(0)\n",
    "        prev1=dummy1\n",
    "        prev2=dummy2\n",
    "        cur=head\n",
    "        while cur:\n",
    "            nextn=cur.next\n",
    "            if cur.val <0:\n",
    "                prev2.next=cur\n",
    "                cur.next=None\n",
    "                prev2=cur\n",
    "                prev1.next=nextn\n",
    "            else:\n",
    "                prev1.next=cur\n",
    "                prev1=cur\n",
    "            cur=nextn\n",
    "        prev1.next=None\n",
    "        prev2.next=None\n",
    "        p,c=None,dummy2.next\n",
    "\n",
    "        while c:\n",
    "            next=c.next\n",
    "            c.next=p\n",
    "            p=c\n",
    "            c=next\n",
    "        d=dummy2.next\n",
    "        if p:\n",
    "            d.next=dummy1.next\n",
    "            dummy2.next=p\n",
    "            return dummy2.next\n",
    "        else:\n",
    "            return dummy1.next\n",
    "\n",
    "        \n",
    "        return dummy2.next if dummy2.next else dummy1.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head \n",
    "        \n",
    "        node = head \n",
    "        values = []\n",
    "\n",
    "        while node:\n",
    "            values.append(node.val)\n",
    "            node = node.next \n",
    "        \n",
    "        values.sort()\n",
    "\n",
    "        node = head \n",
    "        for value in values:\n",
    "            node.val = value \n",
    "            node = node.next \n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      preNode = ListNode(-1, next=head)\n",
    "      cur, pre = head, preNode\n",
    "      neg = tail = None\n",
    "      while cur:\n",
    "        if cur.val >= 0:  pre, cur = cur, cur.next\n",
    "        else:\n",
    "          pre.next = cur.next\n",
    "          cur.next = neg\n",
    "          neg = cur\n",
    "          if not tail: tail = neg\n",
    "          cur = pre.next\n",
    "      if not tail:  return head\n",
    "      tail.next = preNode.next\n",
    "      return neg      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      preNode = ListNode(-1, next=head)\n",
    "      cur, pre = head, preNode\n",
    "      neg = tail = None\n",
    "      while cur:\n",
    "        if cur.val >= 0:  pre, cur = cur, cur.next\n",
    "        else:\n",
    "          pre.next = cur.next\n",
    "          cur.next = neg\n",
    "          neg = cur\n",
    "          if not tail: tail = neg\n",
    "          cur = pre.next\n",
    "      if not tail:  return head\n",
    "      tail.next = preNode.next\n",
    "      return neg      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "'''\r\n",
    "头插法，默认第一个节点已经排好序，从第二个点开始，遇到负数，头插法，非负继续往下\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        prev, curr = head, head.next\r\n",
    "        while curr:\r\n",
    "            if curr.val < 0:\r\n",
    "                t = curr.next\r\n",
    "                prev.next = t\r\n",
    "                curr.next = head\r\n",
    "                head = curr\r\n",
    "                curr = t\r\n",
    "            else:\r\n",
    "                prev, curr = curr, curr.next\r\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        dummy = ListNode(-5001, head)\n",
    "        pre = dummy\n",
    "        p = head\n",
    "        while p:\n",
    "            if p.val < pre.val:\n",
    "                next_cur = p.next\n",
    "                p.next = dummy.next\n",
    "                dummy.next = p\n",
    "                pre.next = next_cur\n",
    "                p = next_cur\n",
    "            else:\n",
    "                pre = p\n",
    "                p = p.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prev, curr = head, head.next\n",
    "        while curr:\n",
    "            if curr.val < 0:\n",
    "                tmp = curr.next\n",
    "                prev.next = tmp\n",
    "                curr.next = head\n",
    "                head = curr\n",
    "                curr = tmp\n",
    "            else:\n",
    "                prev, curr = curr, curr.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      preNode = ListNode(-1, next=head)\n",
    "      cur, pre = head, preNode\n",
    "      neg = tail = None\n",
    "      while cur:\n",
    "        if cur.val >= 0:  pre, cur = cur, cur.next\n",
    "        else:\n",
    "          pre.next = cur.next\n",
    "          cur.next = neg\n",
    "          neg = cur\n",
    "          if not tail: tail = neg\n",
    "          cur = pre.next\n",
    "      if not tail:  return head\n",
    "      tail.next = preNode.next\n",
    "      return neg      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "## Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        left, right = head, head\n",
    "        prev = ListNode(0, head)\n",
    "        while right:\n",
    "            if right.val <= left.val and right != left:\n",
    "                prev.next = right.next\n",
    "                right.next = left\n",
    "                left = right\n",
    "                right = prev.next\n",
    "            else:\n",
    "                prev = right\n",
    "                right = right.next\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        left,right=head,head\n",
    "        prev=ListNode(0,head)\n",
    "        while right:\n",
    "            if right.val<=left.val and right!=left:\n",
    "                prev.next=right.next\n",
    "                right.next=left\n",
    "                left=right\n",
    "                right=prev.next\n",
    "            else:\n",
    "                prev=right\n",
    "                right=right.next\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prev = head\n",
    "        curr = head.next\n",
    "        while curr:\n",
    "            if curr.val < 0:\n",
    "                temp = curr.next\n",
    "                prev.next = temp\n",
    "                curr.next = head\n",
    "                head = curr\n",
    "                curr = temp\n",
    "            else:\n",
    "                prev = curr\n",
    "                curr = curr.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            if cur.val < 0:\n",
    "                tmp = cur.next\n",
    "                pre.next = tmp\n",
    "                cur.next = head\n",
    "                head = cur\n",
    "                cur = tmp\n",
    "            else:\n",
    "                pre, cur = cur, cur.next\n",
    "        return head "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        prev, curr = head, head.next\n",
    "        while curr:\n",
    "            if curr.val < 0:\n",
    "                t = curr.next\n",
    "                prev.next = t\n",
    "                curr.next = head\n",
    "                head = curr\n",
    "                curr = t\n",
    "            else:\n",
    "                prev, curr = curr, curr.next\n",
    "        return head\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/sort-linked-list-already-sorted-using-absolute-values/solutions/1059650/tou-cha-fa-chao-jian-ji-javapython3cgo-s-0sl6/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        lst=[]\n",
    "        while head:\n",
    "            lst.append(head.val)\n",
    "            head=head.next\n",
    "        lst.sort()\n",
    "        dd=ListNode()\n",
    "        current=dd\n",
    "        for i in lst:\n",
    "            current.next=ListNode(i)\n",
    "            current=current.next\n",
    "        return dd.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "      cur = head\n",
    "      l = []\n",
    "      while cur != None:\n",
    "        l.append(cur.val)\n",
    "        cur = cur.next\n",
    "      print(l)\n",
    "      l.sort()\n",
    "      if len(l) == 0: return None\n",
    "      head = ListNode(l[0])\n",
    "      cur = head\n",
    "      cur.next = None\n",
    "      for i in range(1, len(l)):\n",
    "        cur.next = ListNode(l[i])\n",
    "        cur = cur.next\n",
    "        cur.next = None\n",
    "      return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def ListNode2Array(head):\n",
    "    arr = []\n",
    "    while head:\n",
    "        arr.append(head.val)\n",
    "        head = head.next\n",
    "    return arr\n",
    "\n",
    "def Array2ListNode(arr):\n",
    "    cur = head = ListNode()\n",
    "    for x in arr:\n",
    "        cur.next = ListNode(x)\n",
    "        cur = cur.next\n",
    "    return head.next\n",
    "class Solution:\n",
    "    def sortLinkedList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        arr = ListNode2Array(head)\n",
    "        return Array2ListNode(sorted(arr))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
